home *** CD-ROM | disk | FTP | other *** search
/ Software Vault: The Gold Collection / Software Vault - The Gold Collection (American Databankers) (1993).ISO / cdr48 / pas_0593.zip / BOYERMO2.PAS < prev    next >
Pascal/Delphi Source File  |  1993-05-30  |  15KB  |  258 lines

  1. {─ Fido Pascal Conference ────────────────────────────────────────────── PASCAL ─
  2. Msg  : 129 of 132
  3. From : BRIAN PAPE                          1:2250/26.0          02 May 93  03:06
  4. To   : MARK OUELLET
  5. Subj : [1/2] BOYER-MOOR SEAR 1/2
  6. ────────────────────────────────────────────────────────────────────────────────
  7. MO> DS> A few years ago you posted some Turbo Pascal source code for doing
  8. MO> DS> Boyer-Moore searches.  I did save that code but when I tried to compile
  9. MO> DS> it today it would not run.  Would it be too much trouble to ask you to
  10. MO> DS> repost it.  Thank you very much.
  11.  
  12. Well, I'm not Mark, but I've got some code here- It doesn't appear to
  13. have any copyright notices, and I've never tested it, but it does
  14. compile under at least 6.0 and 7.0 (don't have 5.0 & 5.5 installed to
  15. test it on).}
  16.  
  17. { BOYERMO2.PAS (23 January 1988) (Rufus S. Hendon) }
  18.  
  19. {    This unit provides facilities for searching a text for a target using
  20.   the Boyer-Moore search method.  The routine is based on Don Strenczewilk's
  21.   implementation of a variant form of the Boyer-Moore method (his case-
  22.   insensitive version B1, available on CompuServe in file BLINE.ARC in
  23.   Borland BPROGA Data Library 4, uploaded 21 August 1987).  In addition to
  24.   repackaging his routine as a Turbo Pascal 4.0 unit, I have modified it
  25.   (1) to provide protection against endless loops that in the original
  26.   version can arise due to wrap-around of the index used to scan the text
  27.   when the the length of the text approaches the maximum (65521 characters)
  28.   allowed by Turbo Pascal 4.0 for arrays of type CHAR and (2) to improve
  29.   efficiency slightly by removing three instructions (a PUSH, a MOV, and a
  30.   POP) from the comparison loop.
  31.      The text to be searched must be stored in an array of type CHAR or an
  32.   equivalent user-defined type.  The lower bound of the array must be 1.
  33.   The target for which the text is to be searched must be of type STRING.
  34.   The program must also provide a variable for the storage of the shift
  35.   table used by the Boyer-Moore method when it searches the text.  This
  36.   variable must provide 256 bytes of storage; it can, for example, be a
  37.   variable of type ARRAY[CHAR] OF BYTE.  The target variable and the shift-
  38.   table variable must be in the same segment:  they must both be global
  39.   variables (located in the data segment) or both local variables (stored
  40.   in the stack segment).
  41.      Whenever the text is to be searched for a new target, the program must
  42.   call MAKE_BOYER_MOORE_TABLE to create the shift table for the target.
  43.   Thereafter the text can be searched for the target by invoking
  44.   BOYER_MOORE_SEARCH, specifying as arguments the target and its shift
  45.   table as well as the position in the text where the search is to begin.
  46.   If the program maintains multiple target variables and a separate shift
  47.   table and starting-position variable for each target, searches for
  48.   occurrences of the various targets can be underway simultaneously.
  49.      In a call to BOYER_MOORE_SEARCH, the argument associated with the
  50.   parameter START determines the position in the text with which the search
  51.   begins.  To search the entire text, the function would be invoked with
  52.   START = 1.  The function scans the text beginning from the START position
  53.   for the first substring that matches the target specified by the variable
  54.   associated with the parameter TARGET, using the shift table stored in the
  55.   variable associated with the parameter TABLE.  If such a substring is
  56.   found, the function returns the position (array subscript) of the initial
  57.   character of the matching substring; since the array is required to have
  58.   1 as its lower bound, the position returned after a successful search
  59.   will always be greater than 0.  If the function fails to find a matching
  60.   substring, it returns 0.  (If the requirement that the TARGET and TABLE
  61.   variables be in the same segment is violated, the function also returns
  62.   0.)
  63.      When it is required that all occurrences in the text of a given target
  64.   be found, BOYER_MOORE_SEARCH would be invoked in a loop, in which the
  65.   START argument would initially have the value of 1; thereafter, after
  66.   every successful search, the START argument would be reset to the
  67.   position returned by the function plus 1.  The loop would terminate when
  68.   the function reported failure.  The loop would have a general structure
  69.   similar to this:
  70.  
  71.     item := [the target string];
  72.     make_Boyer_Moore_table(item,shift_table);
  73.     scan_beginning := 1;
  74.     search_text_length := length(search_text);
  75.     repeat
  76.       i := Boyer_Moore_search(search_text,scan_beginning,search_text_length,
  77.           item,shift_table);
  78.       if i > 0 then begin
  79.         [do whatever processing is required when the search is successful];
  80.         scan_beginning := i+1
  81.       end
  82.     until i = 0
  83.  
  84.      Note that if the text array can only be referred to by means of a
  85.   pointer, as will be the case if the array is allocated in the heap by
  86.   means of the NEW procedure, the pointer, when used as the first argument
  87.   of BOYER_MOORE_SEARCH, must be dereferenced by writing '^' after it.  If,
  88.   for example, TEXTPTR is a pointer to the text array, the call to the
  89.   search function in the loop just given would take this form:
  90.  
  91.       i := Boyer_Moore_search(textptr^,scan_beginning,search_text_length,
  92.           item,shift_table);
  93.                                                                              }
  94. {============================================================================}
  95. unit BOYERMO2;
  96. {============================================================================}
  97. interface
  98.  
  99. procedure MAKE_BOYER_MOORE_TABLE(var target: string; var table);
  100. { TARGET is the target string for which a text is to be searched.  The
  101.   shift table for the target string is constructed in TABLE, which must be
  102.   a variable providing 256 bytes of storage, e.g. a variable declared as
  103.   ARRAY[CHAR] OF BYTE. }
  104.  
  105. function BOYER_MOORE_SEARCH(var text_array; start, text_length: word;
  106.     var target: string; var table): word;
  107. { TEXT_ARRAY is an array of characters in which a text is stored; the
  108.   text begins in TEXT_ARRAY[1] and is TEXT_LENGTH characters long.  TARGET
  109.   must either be the same variable used as parameter TARGET in an earlier
  110.   call to MAKE_BOYER_MOORE_TABLE or another variable with the same value.
  111.   TABLE must be the variable that was used as parameter TABLE in the same
  112.   call to MAKE_BOYER_MOORE_TABLE.  TARGET and TABLE must be in the same
  113.   segment, i.e. they must both be global variables or both local variables.
  114.   A Boyer-Moore search is performed on the text in TEXT_ARRAY, beginning
  115.   with the character in position START and using shift table TABLE, for
  116.   the first substring that matches TARGET.  If a match is found, the
  117.   position of the first character of the matching substring is returned.
  118.   Otherwise 0 is returned.  A function value of 0 is also returned if TABLE
  119.   and TARGET are not in the same segment. }
  120. {============================================================================}
  121. implementation
  122.  
  123. const
  124.   copy: string = '';
  125. var
  126.   table: array[char] of byte;
  127. {****************************************************************************}
  128. procedure MAKE_BOYER_MOORE_TABLE(var target: string; var table);
  129. { TARGET is the target string for which a text is to be searched.  The
  130.   shift table for the target string is constructed in TABLE, which must be
  131.   a variable providing 256 bytes of storage, e.g. a variable declared as
  132.   ARRAY[CHAR] OF BYTE. }
  133. begin { MAKE_BOYER_MOORE_TABLE }
  134.   inline
  135.     ($1E/              {       push ds            }
  136.      $C5/$76/<target/  {       lds si,[bp+target] }
  137.      $89/$F3/          {       mov bx,si          }
  138.      $8A/$04/          {       mov al, [si]       }
  139.      $88/$C4/          {       mov ah,al          }
  140.      $B9/$80/$00/      {       mov cx,$0080       }
  141.      $C4/$7E/<table/   {       les di,[bp+table]  }
  142.      $89/$FA/          {       mov dx,di          }
  143.      $FC/              {       cld                }
  144.      $F2/$AB/          {       rep stosw          }
  145.      $89/$DE/          {       mov si,bx          }
  146.      $89/$D7/          {       mov di,dx          }
  147.      $46/              {       inc si             }
  148.      $98/              {       cbw                }
  149.      $3C/$01/          {       cmp al,1           }
  150.      $7E/$13/          {       jle done           }
  151.      $48/              {       dec ax             }
  152.      $88/$E1/          {       mov cl,ah          }
  153.      $88/$E7/          {       mov bh,ah          }
  154.      $8A/$1C/          { next: mov bl,[si]        }
  155.      $89/$C2/          {       mov dx,ax          }
  156.      $29/$CA/          {       sub dx,cx          }
  157.      $88/$11/          {       mov [bx+di],dl     }
  158.      $46/              {       inc si             }
  159.      $41/              {       inc cx             }
  160.      $39/$C1/          {       cmp cx,ax          }
  161.      $75/$F2/          {       jne next           }
  162.      $1F)              { done: pop ds             }
  163. end; { MAKE_BOYER_MOORE_TABLE }
  164.  
  165. {****************************************************************************}
  166. function BOYER_MOORE_SEARCH(var text_array; start, text_length: word;
  167.     var target: string; var table): word;
  168. { TEXT_ARRAY is an array of characters in which a text is stored; the
  169.   text begins in TEXT_ARRAY[1] and is TEXT_LENGTH characters long.  TARGET
  170.   must either be the same variable used as parameter TARGET in an earlier
  171.   call to MAKE_BOYER_MOORE_TABLE or another variable with the same value.
  172.   TABLE must be the variable that was used as parameter TABLE in the same
  173.   call to MAKE_BOYER_MOORE_TABLE.  TARGET and TABLE must be in the same
  174.   segment, i.e. they must both be global variables or both local variables.
  175.   A Boyer-Moore search is performed on the text in TEXT_ARRAY, beginning
  176.   with the character in position START and using shift table TABLE, for
  177.   the first substring that matches TARGET.  If a match is found, the
  178.   position of the first character of the matching substring is returned.
  179.   Otherwise 0 is returned.  A function value of 0 is also returned if TABLE
  180.   and TARGET are not in the same segment. }
  181. begin { BOYER_MOORE_SEARCH }
  182.   inline
  183.     ($1E/                  {            push ds                 }
  184.      $33/$C0/              {            xor ax,ax               }
  185.      $C5/$5E/<table/       {            lds bx,[bp+table]   } { If TABLE and  }
  186.      $8C/$D9/              {            mov cx,ds           } { TARGET are in }
  187.      $C5/$76/<target/      {            lds si,[bp+target]  } { different     }
  188.      $8C/$DA/              {            mov dx,ds           } { segments, re- }
  189.      $3B/$D1/              {            cmp dx,cx           } { port failure  }
  190.      $75/$76/              {            jne notfound2       } { at once       }
  191.      $8A/$F4/              {            mov dh,ah               }
  192.      $8A/$14/              {            mov dl,[si]             }
  193.      $80/$FA/$01/          {            cmp dl,1                }
  194.      $7F/$1F/              {            jg boyer                }
  195.      $7C/$6B/              {            jl notfound2            }
  196.      $8A/$44/$01/          {            mov al,[si+1]           }
  197.      $8B/$56/<start/       {            mov dx,[bp+start]       }
  198.      $4A/                  {            dec dx                  }
  199.      $8B/$4E/<text_length/ {            mov cx,[bp+text_length] }
  200.      $2B/$CA/              {            sub cx,dx               }
  201.      $C4/$7E/<text_array/  {            les di,[bp+text_array]  }
  202.      $8B/$DF/              {            mov bx,di               }
  203.      $03/$FA/              {            add di,dx               }
  204.      $FC/                  {            cld                     }
  205.      $F2/$AE/              {            repne scasb             }
  206.      $75/$53/              {            jne notfound2           }
  207.      $97/                  {            xchg ax,di              }
  208.      $2B/$C3/              {            sub ax,bx               }
  209.      $EB/$50/              {            jmp short exit          }
  210.      $FE/$CA/              { boyer:     dec dl                  }
  211.      $03/$F2/              {            add si,dx               }
  212.      $C4/$7E/<text_array/  {            les di,[bp+text_array]  }
  213.      $8B/$CF/              {            mov cx,di               }
  214.      $03/$4E/<text_length/ {            add cx,[bp+text_length] }
  215.      $49/                  {            dec cx                  }
  216.      $4F/                  {            dec di                  }
  217.      $03/$7E/<start/       {            add di,[bp+start]       }
  218.      $03/$FA/              {            add di,dx               }
  219.      $8A/$74/$01/          {            mov dh,[si+1]           }
  220.      $55/                  {            push bp                 }
  221.      $8B/$E9/              {            mov bp,cx               }
  222.      $8A/$EC/              {            mov ch,ah               }
  223.      $FD/                  {            std                     }
  224.      $EB/$05/              {            jmp short comp          }
  225.      $D7/                  { nexttable: xlat                    }
  226.      $03/$F8/              {            add di,ax               }
  227.      $72/$2A/              {            jc notfound             }
  228.      $3B/$EF/              { comp:      cmp bp,di               }
  229.      $72/$26/              {            jb notfound             }
  230.      $26/$8A/$05/          {            mov al,es:[di]          }
  231.      $3A/$F0/              {            cmp dh,al               }
  232.      $75/$F0/              {            jne nexttable           }
  233.      $4F/                  {            dec di                  }
  234.      $8A/$CA/              {            mov cl,dl               }
  235.      $F3/$A6/              {            repe cmpsb              }
  236.      $74/$0D/              {            je found                }
  237.      $8A/$C2/              {            mov al,dl               }
  238.      $2B/$C1/              {            sub ax,cx               }
  239.      $03/$F8/              {            add di,ax               }
  240.      $47/                  {            inc di                  }
  241.      $03/$F0/              {            add si,ax               }
  242.      $8A/$C6/              {            mov al,dh               }
  243.      $EB/$DC/              {            jmp short nexttable     }
  244.      $5D/                  { found:     pop bp                  }
  245.      $C4/$46/<text_array/  {            les ax,[bp+text_array]  }
  246.      $97/                  {            xchg ax,di              }
  247.      $2B/$C7/              {            sub ax,di               }
  248.      $40/                  {            inc ax                  }
  249.      $40/                  {            inc ax                  }
  250.      $EB/$03/              {            jmp short exit          }
  251.      $5D/                  { notfound:  pop bp                  }
  252.      $32/$C0/              { notfound2: xor al,al               }
  253.      $89/$46/$FE/          { exit:      mov [bp-2],ax           }
  254.      $FC/                  {            cld                     }
  255.      $1F)                  {            pop ds                  }
  256. end; { BOYER_MOORE_SEARCH }
  257. {****************************************************************************}
  258. end.